package com.li.algorithm.leetcode.hot100;

import java.util.Arrays;

public class Test15 {
    public void rotate(int[] nums, int k) {
        //无论k为多少，k%len 就是实际需要移动的数量
        int len = nums.length;
        k = k % len;
        //创建一个新数组
        int j = 0;
        //TODO: len-k ~ len 放到 0 ~ k
        //TODO: 0 ~ len-k 放到 k ~ len
        int[] result = new int[len];
        //TODO: len - k ~ len
        for (int i = len - k; i < len; i++) {
            result[j] = nums[i];
            j++;
        }
        //TODO: 0 ~ len - k
        for (int i = 0; i < len - k; i++) {
            result[j] = nums[i];
            j++;
        }
        System.arraycopy(result, 0, nums, 0, len);
    }

    public void rotate2(int[] nums, int k) {
        //TODO: 数组其实是一个环形结构，一圈的长度是 len，每个位置都是挪动 (i + k) % len
        int len = nums.length;
        k = k % len;
        int from = 0, to = -1;
        int temp = nums[from];
        //TODO: len % k == 0 的时候会出现一轮遍历不到的情况
        //len = 6, k = 3， 需要遍历三次
        //len = 6, k = 2，需要遍历两次
        //len = 8, k = 4，需要遍历四次
        //TODO: 故遍历次数为：len 与 k 的最大公约数
        int start = 0;
        int count = 0;
        while (count != len) {
            to = (from + k) % len;
            int replaced = nums[to];
            nums[to] = temp;
            temp = replaced;
            from = to;
            count++;
            if (to == start && count != len) {
                start++;
                from = start;
                temp = nums[from];
            }
        }
        System.out.println(Arrays.toString(nums));
    }

    public void reverse(int[] nums, int begin, int end) {
        int temp;
        while (begin < end) {
            temp = nums[begin];
            nums[begin] = nums[end];
            nums[end] = temp;
            begin++;
            end--;
        }
    }

    public void rotate3(int[] nums, int k) {
        k = k % nums.length;
        //TODO: 反转全部元素
        //TODO: 反转 0 ~ k个元素
        //TODO: 反转 k ~ len个元素
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
        System.out.println(Arrays.toString(nums));
    }

    public static void main(String[] args) {
        Test15 test15 = new Test15();
        test15.rotate3(new int[]{1,2,3,4,5,6,7}, 3);
    }
}
